package monotonous_queue;

/**
 * 最大矩形 <br />
 * 算法：单调栈 + 动态规划 <br />
 * 算出每一行的每个元素在其对应的列上最大的连续 1 的数量 <br />
 * 这样就转化成了 84 题
 *
 * @author yezh
 * @date 2023/8/16 14:22
 */
public class _85 {

    public static int maximalRectangle(char[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int[][] nums = new int[n + 1][m];
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i - 1][j] == '1') nums[i][j] = nums[i - 1][j] + 1;
        int ans = 0, top;
        int[] l = new int[m], r = new int[m];
        int[] stack = new int[m];
        for (int i = 1; i <= n; i++) {
            top = -1;
            for (int j = 0; j < m; j++) {
                r[j] = m;
                while (top != -1 && nums[i][j] < nums[i][stack[top]]) r[stack[top--]] = j;
                stack[++top] = j;
            }
            top = -1;
            for (int j = m - 1; j >= 0; j--) {
                l[j] = -1;
                while (top != -1 && nums[i][j] < nums[i][stack[top]]) l[stack[top--]] = j;
                stack[++top] = j;
            }
            for (int j = 0; j < m; j++) ans = Math.max(ans, nums[i][j] * (r[j] - l[j] - 1));
        }
        return ans;
    }

}
